package 复杂链表的复制;
//题目描述
//输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），
// 请对此链表进行深拷贝，并返回拷贝后的头结点。
// （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
public class Solution
{
    public RandomListNode Clone(RandomListNode pHead)
    {
        //三步，1，在原链表的每个节点后面加复制的链表节点
        //2，添加随机指针
        //3，分离原链表与复制链表
        if (pHead==null)
            return null;
        RandomListNode currentNode=pHead;
        while (currentNode!=null)//A
        {
            RandomListNode cloneNode=new RandomListNode(currentNode.label);//A'
            RandomListNode nextNode=currentNode.next;//B
            currentNode.next=cloneNode;//A-A'
            cloneNode.next=nextNode;//A‘-B
            //前进
            currentNode=nextNode;
        }
        currentNode=pHead;
        //复制随机指针
        while (currentNode!=null)
        {
            currentNode.next.random=currentNode.random==null?null:currentNode.random.next;
            //前进
            currentNode=currentNode.next.next;
        }
        //分离两个链表
        currentNode=pHead;
        RandomListNode pCloneHead=pHead.next;
        while (currentNode!=null)
        {
            RandomListNode cloneNode=currentNode.next;
            currentNode.next=cloneNode.next;
            cloneNode.next=cloneNode.next==null?null:cloneNode.next.next;
            //前进
            currentNode=currentNode.next;
        }
        return pCloneHead;
    }
}
